package 剑指offer;

import 数组和链表.SymbolList;
import 抽象数据类型.ListNode;

/**
 * @description:
 * @author: ywk
 * @date: 2021-03-13
 */
public class 判断是否为回文链表 {
    static ListNode left;
    static int count = 0;

    //判断回文链表
    static boolean isPalidrome(ListNode head) {
        left = head;
        return traverseNode(head);
    }    //后序遍历链表

    static boolean traverseNode(ListNode right) {
        count++;
        if (right == null) {
            return true;
        }
        boolean res = traverseNode(right.getNext());
        res = res && (right.getVal() == left.getVal());
        left = left.getNext();
        return res;
    }    //后续遍历

    static void traverse(ListNode head) {
        if (head == null) {
            return;
        }
        traverse(head.getNext());
        System.out.println(head.getVal());
    }

    public static void main(String[] args) {
        ListNode head = new ListNode();
        ListNode listNode = SymbolList.buildList(new int[]{1, 2, 3, 2, 1});
        traverse(listNode);
        System.out.println(isPalidrome(listNode));
        System.out.println(count);
    }
}
